package com.二叉树2;

import sun.awt.image.ImageWatched;

import java.util.*;

/**
 * Serialize and Deserialize Binary Tree
 *
 * Solution
 * Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
 *
 * Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
 *
 * Example:
 *
 * You may serialize the following tree:
 *
 *     1
 *    / \
 *   2   3
 *      / \
 *     4   5
 *
 * as "[1,2,3,null,null,4,5]"
 * Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
 *
 * Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
 * https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/
 */
public class 正反序列二叉树 {
    static public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null){
                return "[]";
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            List<String> list = new ArrayList<>();
            while (!queue.isEmpty()){
                int size = queue.size();
                for(int i  = 0 ;i<size;i++){
                    TreeNode poll = queue.poll();
                    if(poll==null){
                        list.add(null);
                    }
                    else {
                        list.add(String.valueOf(poll.val));
                        queue.add(poll.left);


                        queue.add(poll.right);
                    }

                }
            }
            //去掉尾巴上null的
            for(int i = list.size()-1;i>=0;i--){
                if(list.get(i)==null){
                    list.remove(i);
                }
                else{
                    break;
                }
            }
            StringBuilder builder = new StringBuilder();
            builder.append("[");
            for (int i = 0; i < list.size(); i++) {
                if(i != 0 ){
                    builder.append(",");
                }
                builder.append(list.get(i));

            }
            builder.append("]");
            return builder.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data.equals("[]")){
                return null;
            }
            List<String> list = new ArrayList<>();
            data = data.substring(1,data.length()-1);
            String[] datas = data.split(",");
            for (int i = 0; i < datas.length; i++) {
                list.add(datas[i]);
            }
            String[] nums = list.toArray(new String[list.size()]);
            TreeNode cur = new TreeNode(Integer.valueOf( nums[0]));

            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(cur);
            for (int i = 1; i < nums.length;) {

                TreeNode tmp = queue.poll();

                if(tmp==null){
                    continue;
                }
                String leftNum = nums[i];

                TreeNode left = null;
                if(!leftNum.equals("null")){
                    left = new TreeNode(Integer.valueOf(leftNum));
                }
                tmp.left = left;
                ++i;
                if (i >= nums.length) {
                    break;
                }
                String rightNum = nums[i];
                TreeNode right = null;
                if(!rightNum.equals("null")){
                    right = new TreeNode(Integer.valueOf(rightNum));
                }
                tmp.right = right;
                queue.add(left);
                queue.add(right);
                i++;
            }

            return cur;
        }



        public static void main(String[] args) {
            Codec codec = new Codec();
            String serialize = codec.serialize(new TreeNode(new Integer[]{5,2,3,null,null,2,4,3,1}));
            TreeNode deserialize = codec.deserialize(serialize);

        }
    }
}
